package com.example.algo.lfu;

import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.Map;

/**
 * 简单的 LFU 算法实现
 */
public class LfuCache {

    // 保存 key value
    private final Map<String, String> keyToVal;
    // 保存 key 的频率
    private final Map<String, Integer> keyToFreq;
    // 每个频率对应的 key 的有序集合
    private final Map<Integer, LinkedHashSet<String>> freqTokeys;

    private final int capacity;
    // 最小的频率
    private int minFreq;

    public LfuCache(int capacity) {
        keyToVal = new HashMap<>();
        keyToFreq = new HashMap<>();
        freqTokeys = new HashMap<>();

        this.capacity = capacity;
        this.minFreq = 0;
    }


    public String get(String key) {
        String val = keyToVal.get(key);
        if (null == val || "".equals(val)) {
            return null;
        }

        // 对应 key 的访问频率加 1
        increaseFrey(key);
        return val;
    }

    public void put(String key, String value) {
        // 先判断 keyToVal 中是否已经有对应的 key
        if (keyToVal.containsKey(key)) {
            // 将最新值替换进去
            keyToVal.put(key, value);
            increaseFrey(key);
        }

        // 判断是否达到最大容量
        if (capacity == keyToVal.size()) {
            removeMinFreqKey();
        }

        keyToVal.put(key, value);
        // 新 key 默认的访问频率为 1
        keyToFreq.put(key, 1);
        freqTokeys.putIfAbsent(1, new LinkedHashSet<>());
        freqTokeys.get(1).add(key);
        // 新添加一个 key 访问频率是 1 ，不出意外的情况下就是最小的访问频率
        this.minFreq = 1;
    }

    /**
     * 访问频率加 1
     */
    public void increaseFrey(String key) {
        int freq = keyToFreq.get(key);
        keyToFreq.put(key, freq + 1);
        freqTokeys.get(freq).remove(key);
        freqTokeys.putIfAbsent(freq + 1, new LinkedHashSet<>());
        freqTokeys.get(freq + 1).add(key);
        if (freqTokeys.get(freq).isEmpty()) {
            freqTokeys.remove(freq);
            // 最小频率的set为空，key被移动到minFreq+1对应的set了
            // 所以minFreq也要加1
            if (this.minFreq == freq) {
                this.minFreq++;
            }
        }
    }

    /**
     * 移除访问频率最低的key
     */
    public void removeMinFreqKey() {
        LinkedHashSet<String> keySets = freqTokeys.get(this.minFreq);
        // 最先添加进去的最先删除
        String deleteKey = keySets.iterator().next();
        keySets.remove(deleteKey);
        if (keySets.isEmpty()) {
            freqTokeys.remove(this.minFreq);
        }

        keyToVal.remove(deleteKey);
        keyToFreq.remove(deleteKey);
    }

    public static void main(String[] args) {
        LfuCache cache = new LfuCache(3);

        cache.put("1", "1");
        cache.put("2", "2");
        cache.put("3", "3");

        // 键 1 的访问频率增加1
        String s1 = cache.get("1");
        System.out.println(s1 != null ? s1 : "null");

        // 缓存容量满了，删除访问频率最低的键 2
        cache.put("4", "4");

        // 键 2 已被删除，返回 null
        String s2 = cache.get("2");
        System.out.println(s2 != null ? s2 : "null");

    }
}
